package com.chenken;

/**
 *	归并排序 
 *	1.不断地将当前序列平均分割成2个子序列，分割到不能再分割为止
 * 	2.不断地将2个子序列合并成一个有序序列，直到最终只剩下一个有序序列
 */
public class MergeSort1 {

	public static void mergeSort(int[] nums) {
		if(nums == null || nums.length == 0) {
			return;
		}
		mergeSort(nums,0,nums.length);
	}
	
	private static void mergeSort(int[] nums, int begin, int end) {
		if(end - begin < 2) return;
		int mid = (begin + end) >> 1;
		mergeSort(nums, begin, mid);//分割
		mergeSort(nums, mid, end);//分割
		merge(nums,begin,mid,end);//合并
	}

	/**
	 * 将[begin,mid)和[mid,end)范围的序列合并成一个有序序列
	 * note:需要merge的2个序列存在于同一个数组中，并且是挨在一起的
	 * 为了更好的完成merge操作，需要将左边的数组[begin,mid)备份出来
	 * @param begin
	 * @param mid
	 * @param end
	 */
	private static void merge(int[] nums,int begin, int mid, int end) {
		int li = 0,le = mid-begin;//左边数组的开始和结束位
		int ri = mid,re = end;//右边数组的开始和结束位
		int ai = begin;
		
		//备份左边数组
		int[] leftBackNums = new int[le-li];
		for(int i = li;i<le;i++) {
			leftBackNums[i] = nums[begin + i];
		}
		//如果左边没有结束
		while(li < le) {
			//如果右边数组的元素比左边数组的元素小
			if(ri < re && nums[ri] < leftBackNums[li]) {
				//将右边数组的元素替换到左边数组位
				nums[ai++] = nums[ri++];
			}else {
				//将左边数组的元素放在右边数组位
				nums[ai++] = leftBackNums[li++];
			}
		}
	}

	public static void main(String[] args) {
		int[] nums = {5,2,1,900,70,55,23,123,522,545,-1,10};
		mergeSort(nums);
		for(int num:nums) {
			System.out.print(num + ",");
		}
	}
}
